Session C-4

C-4: Routing

Conference
8:30 AM — 10:00 AM PDT
Local
May 22 Wed, 11:30 AM — 1:00 PM EDT
Location
Regency C

A Parallel Algorithm and Scalable Architecture for Routing in Benes Networks

Rami Zecharia and Yuval Shavitt (Tel-Aviv University, Israel)

0
Benes/CLOS architectures are common scalable interconnection networks widely used in backbone routers, data centers, on-chip networks, multi-processor systems, and parallel computers. Recent advances in Silicon Photonic technology, especially MZI technology, have made Benes networks a very attractive scalable architecture for optical circuit switches. Numerous routing algorithms for Benes networks were developed starting with linear algorithms having time complexity of \(O(N\log_{2}N)\) steps. Parallel routing algorithms were developed to satisfy the stringent timing requirements of high-performance switching networks and have time complexity of \(O((\log_{2}N)^{2})\). However, their implementation requires \(O(N^2\log_{2}N)\) wires (termed connectivity complexity), and thus are difficult to scale. We present a new routing algorithm for Benes networks combined with a scalable hardware architecture that supports full and partial input permutations. The processing time of the algorithm is limited to \(O((\log_{2}N)^{2})\) steps (iterations) by potentially forfeiting routing of a few input demands; however guarantees close to 100\% utilization for both full and partial input permutations. The algorithm and architecture allow a reduction of the connectivity complexity to \(O(N^{2})\), a \(\log N\) improvement over previous solutions. We prove the algorithm correctness, and analyze its performance analytically and with large scale simulations.
Speaker
Speaker biography is not available.

Nonblocking Conditions for Flex-grid OXC-Clos Networks

Yibei Yao (Shanghai Jiao Tong University, China); Tong Ye (Shanghai JiaoTong University, China); Ning Deng (Huawei Technologies Co., Ltd., China)

0
The emerging multi-fiber optical networks makes it urgent to design large-scale flexible mesh optical cross-connects (OXCs). Though Clos network is the theory for building scalable and cost-effective switching fabrics, the nonblocking conditions of flex-grid optical Clos networks without wavelength conversion remain unknown. This paper studies the nonblocking conditions for the flex-grid OXC-Clos network that is constructed from a number of small-size standard OXCs. We first show that a strictly nonblocking (SNB) OXC-Clos network will incur a high cost, as small-granularity lightpaths may abuse central modules (CMs), rendering them unavailable for large-granularity requests due to frequency conflicts. We thus propose a granularity differential routing (GDR) strategy, the idea of which is to restrict the set of CMs that can be used by the lightpaths of each granularity. Under the GDR strategy, we investigate two system models, granularity-port binding and unbinding models, and prove the wide-sense nonblocking (WSNB) conditions for OXC-Clos networks. We show that the cost of WSNB networks is remarkably smaller than that of SNB networks, and find that the second model can lead to more flexible network-bandwidth utilization than the first model only at a small cost of switching fabrics.
Speaker Yibei Yao (Shanghai Jiao Tong University)



DDR: A Deadline-Driven Routing Protocol for Delay Guaranteed Service

Pu Yang, Tianfang Chang and Lin Cai (University of Victoria, Canada)

0
Time-sensitive applications have become increasingly prevalent in modern networks, necessitating the development of delay-guaranteed routing (DGR) solutions. Finding an optimal DGR solution remains a challenging task due to the NP-hard nature of the problem and the dynamic nature of network traffic. In this paper, we propose Deadline-Driven Routing (DDR), a distributed traffic-aware adaptive routing protocol that addresses the DGR problem. Inspired by online navigation techniques, DDR leverages real-time traffic conditions to optimize routing decisions and ensure on-time packet delivery. By combining network topology-based path generation with real-time traffic knowledge, each router can adjust the forwarding directions of packets to accommodate their heterogeneous latency requirements. Comprehensive simulations on real network topologies demonstrate that DDR can consistently provide delay-guaranteed service in different network topologies with different traffic conditions. Moreover, DDR ensures backward compatibility with legacy devices and existing routing protocols, making it a viable solution for supporting delay-guaranteed service.
Speaker
Speaker biography is not available.

Efficient Algorithm for Region-Disjoint Survivable Routing in Backbone Networks

Erika R. Bérczi-Kovács (ELTE Eötvös Loránd University, Hungary); Péter Gyimesi (Eötvös Loránd University, Hungary); Balázs Vass and János Tapolcai (Budapest University of Technology and Economics, Hungary)

0
Survivable routing is crucial in backbone networks to ensure connectivity, even during failures. At network design, groups of network elements prone to potential failure events are identified. These groups are referred to as Shared Risk Link Groups (SRLGs), and if they are a set of links intersected by a connected region of the plane, we call them regional-SRLGs. A recent study has presented a polynomial-time algorithm for finding a maximum number of regional-SRLG-disjoint paths between two given nodes in a planar topology, with the paths being node-disjoint. However, existing algorithms for this problem are not practical due to their runtime and implementation complexities.

This paper investigates a more general model, the maximum number of non-crossing, regional-SRLG-disjoint paths problem. It introduces an efficient and easily implementable algorithmic framework, leveraging an arbitrarily chosen shortest path finding subroutine for graphs with possibly negative weights. Depending on the subroutine chosen, the framework improves the previous worst-case runtime complexity, or can solve the problem w.h.p. in near-linear expected time.
The proposed framework enables the first additive approximation for a more general NP-hard version of the problem, where the objective is to find the maximum number of regional-SRLG-disjoint paths. We validate our findings through extensive simulations.
Speaker
Speaker biography is not available.

Session Chair

Javier Gomez (National University of Mexico, Mexico)

Enter Zoom
Session C-7

C-7: Congestion Management

Conference
3:30 PM — 5:00 PM PDT
Local
May 22 Wed, 6:30 PM — 8:00 PM EDT
Location
Regency C

BCC: Re-architecting Congestion Control in DCNs

Qingkai Meng, Shan Zhang, Zhiyuan Wang and Tao Tong (Beihang University, China); Chaolei Hu (Tsinghua University, China); Hongbin Luo (Beihang University, China); Fengyuan Ren (Tsinghua University, China)

0
The nature of datacenter traffic is a high volume of bursty tiny flows and standing long flows, which forms the coexistence of transient and persistent congestion. Traditional congestion control (CC) algorithms have inherent limitations in reconciling fast response and high efficiency towards transients with stability and fairness during persistence. In this paper, we provide an insight that re-architects CC with two control laws, tailored to transient and persistent concerns, respectively. Armed with this key insight, we propose bimodal congestion control (BCC), which is founded on two core ideas: (i) Quaternary network state detection, which further distinguishes transient and persistent states in switches, and (ii) Bimodal control law, which is manifested as the transient controller and persistent controller at sources. The transient controller employs a precise control paradigm that halts flows to drain backlogged packets and ramps down/up flow rates to bottleneck bandwidth directly, striving for high efficiency. The persistent controller grounds itself in traditional CC algorithms, inheriting stability and fairness. We implement BCC in the Linux kernel and P4-programmable switch. Evaluations in testbed and simulations show that compared to DCQCN, HPCC, PowerTCP, and Swift, BCC shortens the convergence time by up to 96\% and reduces flow completion time by 14\%\(\sim\)99\%.
Speaker Qingkai Meng(Beihang University)



Reinforcement Learning-based Congestion Control: A Systematic Evaluation of Fairness, Efficiency and Responsiveness

Luca Giacomoni and George Parisis (University of Sussex, United Kingdom (Great Britain))

0
Reinforcement learning (RL)-based congestion control (CC) promises efficient CC in a fast-changing networking landscape, where evolving communication technologies, applications and traffic workloads pose severe challenges to human-derived CC algorithms. RL-based CC is in its early days and substantial research is required to understand existing limitations, identify research challenges and yield deployable solutions. In this paper we present the first reproducible and systematic study of RL-based CC with the aim to highlight strengths and uncover fundamental limitations of the state-of-the-art. We identify challenges in evaluating RL-based CC, establish a methodology for studying said approaches and perform experimentation with RL-based CC approaches that are publicly available. We show that existing approaches can acquire all available bandwidth swiftly and are resistant to non-congestive loss, at the cost of excessive packet loss in normal operation. We show that, as fairness is not embedded into reward functions, existing approaches exhibit unfairness in almost all tested network setups. Finally, we show that existing RL-based CC approaches under-perform when the available bandwidth and end-to-end latency dynamically change. Our codebase and datasets are publicly available with the aim to galvanise the community towards transparency and reproducibility, which have been recognised as crucial for researching and evaluating machine-generated policies.
Speaker
Speaker biography is not available.

Approximation Algorithms for Minimizing Congestion in Demand-Aware Networks

Wenkai Dai (University of Vienna, Austria); Michael Dinitz (Johns Hopkins University, USA); Klaus-Tycho Foerster (TU Dortmund, Germany); Long Luo (University of Electronic Science and Technology of China, China); Stefan Schmid (TU Berlin, Germany)

0
Emerging reconfigurable optical communication technologies enable demand-aware networks: networks whose static topology can be enhanced with demand-aware links optimized towards the traffic pattern the network serves. This paper studies the algorithmic problem of how to jointly optimize the topology and the routing in such demand-aware networks, to minimize congestion. We investigate this problem along two dimensions: (1) whether flows are splittable or unsplittable, and (2) whether routing on the hybrid topology is segregated or not, i.e., whether or not flows either have to use exclusively either the static network or the demand-aware connections. For splittable and segregated routing, we show that the problem is \(2\)-approximable in general, but APX-hard even for uniform demands induced by a bipartite demand graph. For unsplittable and segregated routing, we show an upper bound of \(O\left(\log m/ \log\log m \right)\) and a lower bound of \(\Omega\left(\log m/ \log\log m \right)\) for polynomial-time approximation algorithms, where \(m\) is the number of static links. We further show that under splittable (resp., unsplittable) and non-segregated routing, even for demands of single source (resp., destination), the problem cannot be approximated within a ratio better than \(\Omega\left(\frac{c_{\max}}{c_{\min}} \right)\) unless P=NP, where \(c_{\max}\) (resp., \(c_{\min}\)) denotes the maximum (resp., minimum) capacity.
Speaker Wenkai Dai (University of Vienna)

Wenkai Dai is a final-year PhD student at the Faculty of Computer Science, University of Vienna, Austria, scheduled to finish his PhD in 2024. Previously, he obtained his master's degree in computer science from the University of Saarland, Germany, with a focus on theoretical computer science.

In his doctoral research, he delves into addressing algorithmic challenges inherent to next-generation networking and distributed systems. His work spans a broad spectrum of complexities, ranging from mitigating congestion and optimizing routing lengths in reconfigurable/optical data center networks to robust failover routing protocols. Moreover, he maintains a keen interest in algorithmic problems across various domains, including complexity theory, combinatorial optimization, graph theory, and distributed/online algorithms.


Congestion-aware Routing and Content Placement in Elastic Cache Networks

Jinkun Zhang and Edmund Yeh (Northeastern University, USA)

0
Caching can be leveraged to significantly improve network performance and mitigate congestion. However, characterizing the optimal tradeoff between routing cost and cache deployment cost remains an open problem. In this paper, for a network with arbitrary topology and congestion-dependent nonlinear cost functions, we aim to jointly determine the cache deployment, content placement, and hop-by-hop routing strategies, so that the sum of routing cost and cache deployment cost is minimized. We tackle this NP-hard problem starting with a fixed-routing setting, and then generalize to a dynamic-routing setting. For the fixed-routing setting, a Gradient-combining Frank-Wolfe algorithm with (1,1/2)-approximation is presented. For the general dynamic-routing setting, we obtain a set of KKT conditions, and devise a distributed and adaptive online algorithm based on these conditions. We demonstrate via extensive simulation that our algorithms significantly outperform a number of baseline techniques.
Speaker
Speaker biography is not available.

Session Chair

I-Hong Hou (Texas A&M University, USA)

Enter Zoom


Gold Sponsor


Gold Sponsor


Student Travel Grants


Student Travel Grants


Student Travel Grants

Made with in Toronto · Privacy Policy · INFOCOM 2020 · INFOCOM 2021 · INFOCOM 2022 · INFOCOM 2023 · © 2024 Duetone Corp.